package J3_17;


import java.util.*;

public class test {

    //有一个特殊打字机，它由一个 圆盘 和一个 指针 组成， 圆盘上标有小写英文字母 'a' 到 'z'。只有 当指针指向某个字母时，它才能被键入。指针 初始时 指向字符 'a' 。
    public int minTimeToType(String word) {
        char[] ch = word.toCharArray();
        int count = 0;
        char prev = 'a';
        for (char c : ch) {
            int step = Math.abs(c - prev);
            step = Math.min(step,26 - step);
            count  = count + step + 1;
            prev = c;
        }
        return count;
    }


    //树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
    //
    //给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
    //
    //可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
    //
    //请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
    //
    //树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) {
            ans.add(0);
            return ans;
        }
        List<Integer>[] arr = new List[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new ArrayList<Integer>();
        }
        for (int[] i : edges) {
            arr[i[0]].add(i[1]);
            arr[i[1]].add(i[0]);
        }
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        int x = findLongestNode(0,parent,arr);
        int y = findLongestNode(x,parent,arr);
        parent[x] = -1;
        List<Integer> path = new ArrayList<>();
        while (y != -1) {
            path.add(y);
            y = parent[y];
        }
        path.add(x);
        int len = path.size();
        if (len % 2 == 0) {
            ans.add(path.get(len / 2 - 1));
        }
        ans.add(path.get(len / 2));
        return ans;
    }

    private int findLongestNode(int x, int[] parent, List<Integer>[] arr) {
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[parent.length];
        visited[x] = true;
        queue.offer(x);
        int cur = -1;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            for (int i : arr[cur]) {
                if (!visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                    parent[i] = cur;
                }
            }
        }
        return cur;
    }
}
